package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/21 14:21
 * @description <p>二维子矩阵的数字之和</p>
 */

/**
 * 题目：输入一个二维矩阵，如何计算给定左上角坐标和右下角坐标的
 * 子矩阵的数字之和？对于同一个二维矩阵，计算子矩阵的数字之和的函数
 * 可能由于输入不同的坐标而被反复调用多次。例如，输入图 2.1 中的二维矩
 * 阵，以及左上角坐标为(2, 1)和右下角坐标为(4, 3)的子矩阵，该函数输出 8
 */
public class toOffer2_3_13 {

    //sums里面的每个数据存储的是，该对应点位与[0][0]构成的矩阵内的数据值的和
    private int[][] sums;

    public toOffer2_3_13(int[][] matrix) {
        //判断传进来的数组是否为空，为空返回空
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        //方便后续处理，sums设置大一点，给第一行和第一列都添加0
        sums = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {
            int rowSum = 0;
            for (int j = 0; j < matrix[0].length; j++) {
                rowSum += matrix[i][j];
                //按照行来计算：sum[x][y]=sum[x-1][y] + ([x][1]+[x][2]+···+[x][y])
                //即 第x行第y列的数 = 前面的x-1行的所有数 + 第x行的所有数
                sums[i + 1][j + 1] = sums[i][j + 1] + rowSum;
            }
        }
    }

    /**
     * 计算每个矩阵（左上点（row1，col1）和右下点（row2，col2））里的所有数据的值
     *
     * @param row1
     * @param col1
     * @param row2
     * @param col2
     * @return
     */
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row2 + 1][col1] - sums[row1][col2 + 1] + sums[row1][col1];
    }

    /**
     * 对toOffer2_3_13这个类进行调用
     * 0 0 0 0 0 0
     * 0 3 0 1 4 2
     * 0 5 6 3 2 1
     * 0 1 2 0 1 5
     * 0 4 1 0 1 7
     * 0 1 0 3 0 5
     */
    public static void main(String[] args) {
        int[][] matrix = {{3, 0, 1, 4, 2}, {5, 6, 3, 2, 1}, {1, 2, 0, 1, 5}, {4, 1, 0, 1, 7}, {1, 0, 3, 0, 5}};
        toOffer2_3_13 numMatrix = new toOffer2_3_13(matrix);
        System.out.println(numMatrix.sumRegion(2, 1, 4, 3));
        System.out.println(numMatrix.sumRegion(1, 1, 2, 2));
    }
}
